//
// Created by SXL on 2025/9/1.
//
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
#include <climits>
#include <string>
#include <cmath>
#include <sstream>
#include <set>
#include <unordered_map>
#include <stack>
using namespace std;
#define ll long long
//8.30
void func1() {
    unsigned ll n,m;
    cin>>n>>m;
    int cur=0;
    unsigned ll temp=n;
    set<unsigned ll >st;
    st.insert(temp);
    if (temp%2==0) {
        temp = temp>>1;
    }else {
        temp=temp*3+1;
    }
    while (st.count(temp)==0) {
        st.insert(temp);
        cur++;
        if (temp%2==0) {
            temp = temp>>1;
        }else {
            temp=temp*3+1;
        }
    }
    unsigned ll step=0,x=n;
    while (x!=temp) {
        if (x%2==0) {
            x = x>>1;
        }else {
            x=x*3+1;
        }
        step++;
    }

    if (m>step) {
        m=(m-step)%(st.size()-step);
        n=x;
    }

    while (m--) {
        if (n%2==0) {
            n=n>>1;
        }else {
            n=n*3+1;
        }
    }
    cout<<n;
}

//数论  一个有理数是否能够在k禁止下是有限小数
int gcd(unsigned ll p,unsigned ll  q) {
    return q==0?p:gcd(q,p%q);
}
void func2() {
    int n;
    cin>>n;
    while(n--) {
        unsigned ll  p,q,k;
        cin>>p>>q>>k;
        unsigned ll  g=gcd(p,q);
        unsigned ll  qp=q/g;

        while (qp>1) {
            unsigned ll gg=gcd(qp,k);
            if (gg==1) {
                break;
            }
            qp/=gg;
        }
        cout<<(qp==1?"yes":"no")<<endl;
    }
}

//8.23 1 签到题
void func3() {
    int n,m;
    cin>>n>>m;
    unsigned ll ans=0;
    while(n--) {
        int x,y;
        cin>>x>>y;
        int big =max(x,y);
        int small =min(x,y);
        if (big<=m) {
            ans+=small;
        }else {
            ans+=big;
        }
    }
    cout<<ans<<endl;
    return 0;
}

//8.23 2  数论 求ai&aj =x 求所有的a  这里将x划分为 0位 1位 然后分析应该放入怎么样的a
void func4() {

        int n;
        cin>>n;
        vector<unsigned ll> arr;
        while(n--) {
            vector<unsigned ll> ans;
            int x;
            cin>>x;
            ans.push_back(x);
            //获取x为0的位置
            //然后判断x为0的位置上
            for (int p=0;p<20;p++) {
                //如果x的第p位为0，则放入将这一位改成1的数
                if (((x>>p)&1)==0) {
                    ans.push_back(x|(1<<p));
                }
            }
            cout<<ans.size()<<endl;
            for (auto a:ans) {
                cout<<a<<" ";
            }
            cout<<endl;
        }

}

//8.23   四个集合 分开算超超时 需要重新进行分开算 因子可以^1/2的时间算出来  倍数直接利用集合算  需要减去AnB的内容
void func5() {
    int n,x,y;
    cin>>n>>x>>y;
    unsigned ll ans=0;
    set<unsigned ll> st;
    //因子
    for (unsigned ll i=1;i*i<=x;i++) {
        if (x%i==0) {
            if (i<=n&&st.count(i)==0) {
                st.insert(i);
            }
            unsigned ll temp = x/i;
            if (temp<=n&&st.count(temp)==0) {
                st.insert(temp);
            }
        }
    }
    for (unsigned ll i=1;i*i<=y;i++) {
        if (y%i==0) {
            if (i<=n&&st.count(i)==0) {
                st.insert(i);
            }
            unsigned ll temp = y/i;
            if (temp<=n&&st.count(temp)==0) {
                st.insert(temp);
            }
        }
    }
    unsigned ll count=0;
    for (auto a:st) {
        if (a%x!=0&&a%y!=0) {
            count++;
        }
    }

    unsigned ll ans1=0,ans2=0,g=0,ans3=0;
    ans1 = n/x;
    ans2 = n/y;
    g=gcd(x,y);
    if (g<=n) {
        ans3=n/((x/g)*y);
    }else ans3=0;

    cout<< count+ans1+ans2-ans3<<endl;

}

//签到题 8.9-1
void func6() {
    int n,m;
    cin>>n>>m;
    string s;
    cin>>s;
    while (m--) {
        int op=0;
        char l1,l2;
        cin>>op>>l1>>l2;
        if (op==1) {
            for (auto &c:s) {
                if (c>='a' && c<='z'&&c>=l1&&c<=l2) {
                    c+='A'-'a';
                }
            }
        }else {
            for (auto &c:s) {
                if (c>='A' && c<='Z'&&c>=l1&&c<=l2) {
                    c-='A'-'a';
                }
            }
        }
    }
    cout<<s<<endl;
}

//https://codefun2000.com/p/P3345  dfs 注意什么时候算加入 子节点和当前节点的乘积直接算到总的答案里
//向上返回的只算以当前节点结尾的，因此只算加法
struct Node {
    int num;
    int col;
    vector<int> children;
};
int ans=0;
unsigned ll dfs(map<int,Node*> &mp,Node *node) {
    if (node==nullptr) return 0;
    // if (node->children.size()==0)return 1;
    unsigned ll sum=1;
    vector<unsigned ll> chilsum;
    for (int i=0;i<node->children.size();i++) {
        auto temp = dfs(mp,mp[node->children[i]]);
        if (node->col!=mp[node->children[i]]->col) {
            chilsum.push_back(temp);
            sum+=temp;
        }

    }
    ans+=sum;
    unsigned ll res=sum;
    for (int i=0;i<chilsum.size();i++) {
        for (int j=i+1;j<chilsum.size();j++) {
            ans+=chilsum[i]*chilsum[j];
        }
    }

    return sum;
}
void func7() {
    int n;
    cin>>n;
    if (n==1) {
        cout<<1<<endl;
        return 0;
    }
    map<int,Node*> mp;
    string color;
    int father=0;
    for (int i = 1; i < n; i++) {

        int u,v;
        cin>>u>>v;
        if (father==0)
            father=u;
        if (mp.find(u) == mp.end()) {
            mp[u] = new Node();
            mp[u]->num = u;
            mp[u]->children.push_back(v);
            if (mp.find(v) == mp.end()) {
                mp[v] = new Node();
                mp[v]->num = v;
            }
        }else {
            mp[u]->children.push_back(v);
            if (mp.find(v) == mp.end()) {
                mp[v] = new Node();
                mp[v]->num = v;
            }
        }
    }
    getline(cin,color);
    cin>>color;
    for (int i = 1; i <= n; i++) {
        if (color[i-1]=='R') {
            mp[i]->col =1;
        }else {
            mp[i]->col =0;
        }
    }
    dfs(mp,mp[father]);
    cout<<ans<<endl;
}
//https://codefun2000.com/p/P1873 简单题 注意逻辑
void func8() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    unsigned ll ans=0;
    vector<int> arr(1000,0);

    while (n--) {
        string temp;
        cin >> temp;
        arr[temp.size()]++;
    }
    for (int i=1;i<s.size();i++) {
        ans+=arr[i];
    }
    cout<<ans+1<<" ";
    ans+=arr[s.size()];
    cout<<ans<<endl;
}